#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());

        vector<vector<int>> res;

        for (int k = 0; k < nums.size() - 2; k++)
        {
            if (nums[k] > 0)
            {
                break;
            }
            if (k > 0 && nums[k] == nums[k - 1])
            {
                continue;
            }

            int i = k + 1, j = nums.size() - 1;

            while (i < j)
            {
                int sum = nums[k] + nums[i] + nums[j];
                if (sum < 0)
                {
                    while (i < j && nums[i] == nums[++i])
                    {
                    }
                }
                else if (sum > 0)
                {
                    while (i < j && nums[j] == nums[--j])
                    {
                    }
                }
                else
                {
                    res.push_back({nums[k],nums[i],nums[j]});
                    while (i < j && nums[i] == nums[++i])
                        ;
                    while (i < j && nums[j] == nums[--j])
                        ;
                }
            }
        }
        return res;
    }
};

int main(int argc, char const *argv[])
{

    return 0;
}
